In a graph database, entities are presented as nodes and relationships between those entities are presented as edges in a view of the relational graph maintained by the graph database. The relational graph may be periodically queried by users via graph queries to learn about the relationships between entities. For example, a user may issue a graph query to find friends or contacts within a social network, the documents that a given user has interacted with, the users that a given document has been accessed by, the entities that satisfy various search criteria, etc. As will be appreciated, the relational graph changes as data are added, changed, and removed, and the results of the graph queries may change as a result. Graph queries, however, are computationally expensive to run and therefore keeping the results of graph queries up-to-date in light of changes to the underlying relational graph may require computing devices accessing or hosting the graph database to expend significant processing or storage resources to run repeated graph queries or to run change monitors on every node.